home *** CD-ROM | disk | FTP | other *** search
/ Programming Languages Suite / ProgramD2.iso / Borland / Borland C++ V5.02 / CLASSSRC.PAK / BINIMP.CPP next >
C/C++ Source or Header  |  1997-05-06  |  9KB  |  325 lines
  1. //----------------------------------------------------------------------------
  2. // Borland BIDS Container Library
  3. // Copyright (c) 1993, 1997 by Borland International, All Rights Reserved
  4. //
  5. //$Revision:   5.9  $
  6. //
  7. //----------------------------------------------------------------------------
  8. #include <classlib/pch.h>
  9. #include <winsys/wsysinc.h>   // needed here only to reduce nesting for MSVC
  10. #include <classlib/binimp.h>
  11.  
  12. TBinarySearchTreeBase::TBinarySearchTreeBase() :
  13.     Root(0),
  14.     ItemsInContainer(0)
  15. {
  16. }
  17.  
  18. int TBinarySearchTreeBase::InsertNode( BinNode *node )
  19. {
  20.     BinNode *Current = Root;
  21.     BinNode *Parent = 0;
  22.     while( Current )
  23.         {
  24.         Parent = Current;
  25.         Current = LessThan( node, Current ) ? Current->Left : Current->Right;
  26.         }
  27.     if( Parent == 0 )
  28.         Root = node;
  29.     else
  30.         {
  31.         if( LessThan( node, Parent ) )
  32.             Parent->Left = node;
  33.         else
  34.             Parent->Right = node;
  35.         }
  36.     ItemsInContainer++;
  37.     return 1;
  38. }
  39.  
  40. int TBinarySearchTreeBase::RemoveNode( BinNode *node, int del )
  41. {
  42.     BinNode *Current = Root;
  43.     BinNode *Parent = 0;
  44.     while( Current )
  45.         {
  46.         if( EqualTo( node, Current ) )
  47.             return RemNode( Current, Parent, del );
  48.         else
  49.             {
  50.             Parent = Current;
  51.             Current = LessThan( node, Current ) ? Current->Left :
  52.                                                   Current->Right;
  53.             }
  54.         }
  55.     return 0;
  56. }
  57.  
  58. TBinarySearchTreeBase::BinNode *TBinarySearchTreeBase::FindNode( BinNode *node )
  59. {
  60.     BinNode *Current = Root;
  61.     while( Current )
  62.         {
  63.         if( EqualTo( node, Current ) )
  64.             return Current;
  65.         else
  66.             Current = LessThan( node, Current ) ? Current->Left :
  67.                                                   Current->Right;
  68.         }
  69.     return 0;
  70. }
  71.  
  72. int TBinarySearchTreeBase::RemNode( BinNode *node, BinNode *parent, int del )
  73. {
  74.     // See R. Sedgewick, "Algorithms, 2nd edition",
  75.     //   Addison-Wesley 1988, p.210.
  76.     BinNode *Original = node;
  77.     if( Original->Right == 0 )
  78.         node = node->Left;
  79.     else if( Original->Right->Left )
  80.         {
  81.         BinNode *Current = Original->Right;
  82.         while( Current->Left->Left )
  83.             Current = Current->Left;
  84.         node = Current->Left;
  85.         Current->Left = node->Right;
  86.         node->Left = Original->Left;
  87.         node->Right = Original->Right;
  88.         }
  89.     else
  90.         {
  91.         node = node->Right;
  92.         node->Left = Original->Left;
  93.         }
  94.     if( parent == 0 )
  95.         Root = node;
  96.     else if( LessThan( Original, parent ) )
  97.         parent->Left = node;
  98.     else
  99.         parent->Right = node;
  100.  
  101.     DeleteNode( Original, del );
  102.     ItemsInContainer--;
  103.     return 1;
  104. }
  105.  
  106. #if defined(BI_NAMESPACE)
  107. namespace ClassLib {
  108. #endif
  109.  
  110. class TBinaryTreeKiller : public TBinaryTreeInternalIteratorBase
  111. {
  112.  
  113. public:
  114.  
  115.     TBinaryTreeKiller( TBinarySearchTreeBase& tree, int del ) :
  116.         TBinaryTreeInternalIteratorBase( tree, TBinarySearchTreeBase::PostOrder ),
  117.         Del(del) {}
  118.  
  119. private:
  120.  
  121.     virtual void Apply( TBinarySearchTreeBase::BinNode _FAR *node,
  122.                         TBinarySearchTreeBase::BinNode _FAR *parent );
  123.  
  124.     int Del;
  125.  
  126.     TBinaryTreeKiller( const TBinaryTreeKiller& );
  127.     const TBinaryTreeKiller& operator = ( const TBinaryTreeKiller& );
  128.  
  129. };
  130.  
  131. #if defined(BI_NAMESPACE)
  132. }     // namespace ClassLib
  133. #endif
  134.  
  135. void TBinaryTreeKiller::Apply( TBinarySearchTreeBase::BinNode _FAR *node,
  136.                            TBinarySearchTreeBase::BinNode _FAR *parent )
  137. {
  138.     Tree().RemNode( node, parent, Del );
  139. }
  140.  
  141. void TBinarySearchTreeBase::Flush( int del )
  142. {
  143.     if( Root != 0 )
  144.         TBinaryTreeKiller( *this, del ).Iterate();
  145. }
  146.  
  147. void TBinaryTreeInternalIteratorBase::Iterate()
  148. {
  149.     TBinarySearchTreeBase::BinNode _FAR *Current = Node;
  150.     TBinarySearchTreeBase::BinNode _FAR *Prev = 0;
  151.     TBinarySearchTreeBase::BinNode _FAR *Next;
  152. step2:
  153.     if( Order == TBinarySearchTreeBase::PreOrder )
  154.         Apply( Current, 0 );
  155.     Next = Current->Left;
  156.     if( Next != 0 )
  157.         {
  158.         Current->Left = Prev;
  159.         Prev = Current;
  160.         Current = Next;
  161.         goto step2;
  162.         }
  163. step4:
  164.     if( Order == TBinarySearchTreeBase::InOrder )
  165.         Apply( Current, 0 );
  166.     Next = Current->Right;
  167.     if( Next != 0 )
  168.         {
  169.         Current->Right = Prev;
  170.         Prev = Current;
  171.         Current = Next;
  172.         goto step2;
  173.         }
  174. step6:
  175.     if( Prev == 0 )
  176.         {
  177.         if( Order == TBinarySearchTreeBase::PostOrder )
  178.             Apply( Current, 0 );
  179.         return;
  180.         }
  181.     if( Tree().LessThan( Current, Prev ) )
  182.         {
  183.         TBinarySearchTreeBase::BinNode _FAR *Temp = Current;
  184.         Next = Prev->Left;
  185.         Prev->Left = Current;
  186.         Current = Prev;
  187.         Prev = Next;
  188.         if( Order == TBinarySearchTreeBase::PostOrder )
  189.             Apply( Temp, Current );
  190.         goto step4;
  191.         }
  192.     else
  193.         {
  194.         TBinarySearchTreeBase::BinNode _FAR *Temp = Current;
  195.         Next = Prev->Right;
  196.         Prev->Right = Current;
  197.         Current = Prev;
  198.         Prev = Next;
  199.         if( Order == TBinarySearchTreeBase::PostOrder )
  200.             Apply( Temp, Current );
  201.         goto step6;
  202.         }
  203. }
  204.  
  205. TBinaryTreeExternalIteratorBase::TBinaryTreeExternalIteratorBase( TBinarySearchTreeBase& tree, TBinarySearchTreeBase::IteratorOrder order ) :
  206.     Stack( new TStackAsList<TBinarySearchTreeBase::BinNode _BIDSFAR *> ),
  207.     Tree(&tree),
  208.     Current( tree.Root ),
  209.     Order( order )
  210. {
  211.     Restart();
  212. }
  213.  
  214. TBinaryTreeExternalIteratorBase::~TBinaryTreeExternalIteratorBase()
  215. {
  216.     delete Stack;
  217. }
  218.  
  219. void TBinaryTreeExternalIteratorBase::Restart()
  220. {
  221.     Stack->Flush();
  222.     Current = Tree->Root;
  223.     LeftVisited = RightVisited = 0;
  224.     Processed = 0;
  225. }
  226.  
  227. TBinarySearchTreeBase::BinNode *TBinaryTreeExternalIteratorBase::Next()
  228. {
  229.     if( Current == 0 )
  230.         return 0;
  231.     for(;;)
  232.         {
  233.         if( Order == TBinarySearchTreeBase::PreOrder && !Processed )
  234.             {
  235.             Processed = 1;
  236.             return Current;
  237.             }
  238.  
  239.         if( Current->Left != 0 && !LeftVisited )
  240.             {
  241.             Stack->Push( Current );
  242.             Current = Current->Left;
  243.             LeftVisited = RightVisited = 0;
  244.             Processed = 0;
  245.             }
  246.         else if( Current->Right != 0 && !RightVisited )
  247.             {
  248.             TBinarySearchTreeBase::BinNode *Res = 0;
  249.             if( Order == TBinarySearchTreeBase::InOrder )
  250.                 Res = Current;
  251.             Stack->Push( Current );
  252.             Current = Current->Right;
  253.             LeftVisited = RightVisited = 0;
  254.             Processed = 0;
  255.             if( Res != 0 )
  256.                 return Res;
  257.             }
  258.         else
  259.             {
  260.             if( Stack->IsEmpty() )
  261.                 {
  262.                 if( Processed == 0 )
  263.                     {
  264.                     Processed = 1;
  265.                     }
  266.                 else
  267.                     {
  268.                     Current = 0;
  269.                     }
  270.                 return Current;
  271.                 }
  272.             else
  273.                 {
  274.                 TBinarySearchTreeBase::BinNode *Res;
  275.                 switch( Order )
  276.                     {
  277.                     case TBinarySearchTreeBase::PreOrder:
  278.                         // This node has already been
  279.                         // processed, so we have further to go.
  280.                         Res = 0;
  281.  
  282.                         // This node's parent has
  283.                         // already been processed
  284.                         Processed = 1;
  285.  
  286.                         break;
  287.  
  288.                     case TBinarySearchTreeBase::InOrder:
  289.                         if( IsInOrder() )
  290.                             {
  291.                             // This node needs to be processed.
  292.                             Res = Current;
  293.                             }
  294.                         else
  295.                             {
  296.                             // Node has already been processed.
  297.                             Res = 0;
  298.                             }
  299.                         // If we're the right-hand child, our parent
  300.                         // has already been processed.
  301.                         Processed = Stack->Top()->Right == Current;
  302.  
  303.                         break;
  304.  
  305.                     case TBinarySearchTreeBase::PostOrder:
  306.                         // This node needs to be processed.
  307.                         Res = Current;
  308.  
  309.                         // This node's parent has not been processed.
  310.                         Processed = 0;
  311.  
  312.                         break;
  313.                     }
  314.  
  315.                 LeftVisited = 1;
  316.                 RightVisited = Stack->Top()->Right == Current;
  317.                 Current = Stack->Pop();
  318.                 if( Res != 0 )
  319.                     return Res;
  320.                 }
  321.             }
  322.         }
  323. }
  324.  
  325.